package LeetCode;

import java.util.*;

public class LC_373_FindKPairswithSmallestSums {

    public static void main(String[] args) {

    }

    public class Solution {
        private class entry {
            int[] key;
            int val;

            entry(int[] key, int val) {
                this.key = key;
                this.val = val;
            }
        }

        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<int[]> ret = new ArrayList<>();
            if (nums1 == null || nums2 == null || k <= 0) return ret;
            PriorityQueue<entry> pq = new PriorityQueue<entry>(k, (e1, e2) -> -1 * (e1.val - e2.val));
            for (int aNums1 : nums1) {
                for (int aNums2 : nums2) {
                    int[] key = new int[2];
                    key[0] = aNums1;
                    key[1] = aNums2;
                    pq.offer(new entry(key, key[0] + key[1]));
                    if (pq.size() > k) pq.poll();
                }
            }
            while (!pq.isEmpty()) ret.add(pq.poll().key);
            ret.sort((o1, o2) -> o1[0] + o1[1] - o2[0] - o2[1]);
            return ret;
        }
    }

}